


#include "qe_bitmap.h"
#include "qe_memory.h"
#include "qe_assert.h"



qe_bool qe_bitmap_empty(qe_bitmap *map, qe_uint bits)
{
	int k, lim = bits/QE_BITS_PER_LONG;
	for (k = 0; k < lim; ++k)
		if (map[k])
			return qe_false;

	if (bits % QE_BITS_PER_LONG)
		if (map[k] & QE_BITMAP_LAST_WORD_MASK(bits))
			return qe_false;

	return qe_true;
}

qe_bool qe_bitmap_full(qe_bitmap *map, qe_uint bits)
{
	int k, lim = bits/QE_BITS_PER_LONG;
	for (k = 0; k < lim; ++k)
		if (~map[k])
			return qe_false;

	if (bits % QE_BITS_PER_LONG)
		if (~map[k] & QE_BITMAP_LAST_WORD_MASK(bits))
			return qe_false;

	return qe_true;
}

void qe_bitmap_set(qe_bitmap *map, qe_uint start, qe_uint nr)
{
	unsigned long *p = map + QE_BITS_WORD(start);
	const int size = start + nr;
	int bits_to_set = QE_BITS_PER_LONG - (start % QE_BITS_PER_LONG);
	unsigned long mask_to_set = QE_BITMAP_FIRST_WORD_MASK(start);

	while (nr - bits_to_set >= 0) {
		*p |= mask_to_set;
		nr -= bits_to_set;
		bits_to_set = QE_BITS_PER_LONG;
		mask_to_set = ~0UL;
		p++;
	}
	if (nr) {
		mask_to_set &= QE_BITMAP_LAST_WORD_MASK(size);
		*p |= mask_to_set;
	}
}

void qe_bitmap_clear(qe_bitmap *map, qe_uint start, qe_uint nr)
{
	unsigned long *p = map + QE_BITS_WORD(start);
	const int size = start + nr;
	int bits_to_clear = QE_BITS_PER_LONG - (start % QE_BITS_PER_LONG);
	unsigned long mask_to_clear = QE_BITMAP_FIRST_WORD_MASK(start);

	while (nr - bits_to_clear >= 0) {
		*p &= ~mask_to_clear;
		nr -= bits_to_clear;
		bits_to_clear = QE_BITS_PER_LONG;
		mask_to_clear = ~0UL;
		p++;
	}
	if (nr) {
		mask_to_clear &= QE_BITMAP_LAST_WORD_MASK(size);
		*p &= ~mask_to_clear;
	}
}

#define nbits_small(nbits) \
	(__builtin_constant_p(nbits) && (nbits) <= QE_BITS_PER_LONG)

void qe_bitmap_zero(qe_bitmap *dst, qe_uint nbits)
{
	if (nbits_small(nbits))
		*dst = 0UL;
	else {
		int len = QE_BITS_TO_LONG(nbits) * sizeof(qe_bits);
		qe_memset(dst, 0, len);
	}
}

void qe_bitmap_fill(qe_bitmap *dst, qe_uint nbits)
{
	int nlongs = QE_BITS_TO_LONG(nbits);
	if (!nbits_small(nbits)) {
		int len = (nlongs - 1) * sizeof(unsigned long);
		qe_memset(dst, 0xFF, len);
	}
	dst[nlongs - 1] = QE_BITMAP_LAST_WORD_MASK(nbits);
}

qe_bitmap *qe_bitmap_new(qe_uint num_bits)
{
	qe_bitmap *map;

	if (!num_bits) {
		return QE_NULL;
	}

	map = qe_new_n(qe_bitmap, QE_BITS_TO_LONG(num_bits));
	qe_assert(map != QE_NULL);
	qe_memset(map, 0x0, sizeof(qe_bitmap) * QE_BITS_TO_LONG(num_bits));
	return map;
}